package Simple3;

import java.util.Stack;



public class Solution {
	

	  public class TreeNode {
	      int val;
	      TreeNode left;
	      TreeNode right;
	      TreeNode(int x) { val = x; }
	  }
	 
	/**
	 * Return if s and p is the same, such as s=aaa,p=a*
	 * @param s
	 * @param p
	 * @return
	 */
	public boolean isMatch(String s, String p) {
        if(p.isEmpty()) return s.isEmpty();
        return helper(s,p,0,0);
    }
	public boolean helper(String s, String p, int i, int j){
		if(p.length()==j) return s.length()==i;
		if(p.length()-1==j || p.charAt(j+1)!='*'){
			if(s.length()==i) return false;
			return (p.charAt(j)==s.charAt(i) || p.charAt(j)=='.') && helper(s, p, ++i, ++j);
		}
		
		while(i<s.length() && (p.charAt(j)==s.charAt(i) || p.charAt(j)=='.')){
			if(helper(s, p, i++, j+2)){
				return true;
			}
		}
		return helper(s, p, i, j+2);
	}

	/**
	 * Return divident/divisor.
	 * @param dividend
	 * @param divisor
	 * @return
	 */
	public int divide(int dividend, int divisor) {
		assert(divisor!=0);
        if(dividend==0) return 0;
        int ret = 0;
        boolean isminus = ((dividend^divisor)>>>31) == 1;
        long a = Math.abs((long)dividend);
        long b = Math.abs((long)divisor);
        while(a>=b){
            int i=1;
            while(a>=(b<<i))
            	i++;
            i--;
            ret |= (1<<i);
            a -= (b<<i);
        }
        return isminus ? -ret : ret;
        
    }
	
	/**
	 * Leetcode candy problem
	 * @param ratings
	 * @return
	 */
	public int candy(int[] ratings) {
        int n=ratings.length;
        int[] can = new int[n];
        int ret=0;
        for(int i=0;i<n;can[i++]=1);
        
        for(int i=1;i<n;++i){
            if(ratings[i]>ratings[i-1])
                can[i]=can[i-1]+1;
        }
        for(int i=n-2;i>=0;i--){
            if(can[i]<=can[i+1] && ratings[i]>ratings[i+1])
                can[i]=can[i+1]+1;
            ret+=can[i];
        }
        ret+=can[n-1];
        
        return ret;
    }

	/**
	 * Leetcode sumNumbers problem
	 * @param root
	 * @return
	 */
	public int sumNumbers(TreeNode root) {
        return helper(root,0);
    }  
    public int helper(TreeNode root, int sum){
        if(root==null) return 0;
        if(root.left==null && root.right==null) 
            return sum*10+root.val;
        else{
            return helper(root.left,sum*10+root.val)+helper(root.right,sum*10+root.val);
        }
    }

    /**
     * Leetcode polish represent problem.
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].matches("[\\d]+")) {
                stack.push(Integer.parseInt(tokens[i]));
            } 
            else {
                int op2 = stack.pop();
                int op1 = stack.pop();
                int result = 0;
                switch (tokens[i]) {
                    case "+":
                        result = op1 + op2;
                        break;
                    case "-":
                        result = op1 - op2;
                        break;
                    case "*":
                        result = op1 * op2;
                        break;
                    case "/":
                        result = op1 / op2;
                        break;
                    default:break;
                }
                stack.push(result);
            }
        }
        return stack.pop();
    }
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Solution test = new Solution();
//		int[] ratings = {2,1};
//		System.out.println(test.isMatch("aa", "a*"));
//		System.out.println(test.divide(-1010369383, -2147483648));
//		System.out.println(test.candy(ratings));
		
//		TreeNode t1 = test.new TreeNode(1);
//		TreeNode t2 = test.new TreeNode(0);
//		t1.left=t2;
//		System.out.println(test.sumNumbers(t1));
		
		String[] polish ={"4", "1", "+", "2", "*"};
		System.out.println(test.evalRPN(polish));
		
	}

}
